package wxk.interview.sort;

/**
 * 快速排序
 * 快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。
 * 步骤为：
 * 1.从数列中挑出一个元素，称为"基准"（pivot），
 * 2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
 * 3.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
 * <p>
 * 理解篇 挖坑填数+分治法
 * 1．i =L; j = R; 将基准数挖出形成第一个坑a[i]。
 * <p>
 * 2．j--由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
 * <p>
 * 3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
 * <p>
 * 4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。
 *
 * @author wangxuekai
 * @version 1.0
 * @date 2017/3/4.
 */
public class QuickSort extends AbstractSort {
    public void sort(int[] arr) {
        doSort(arr, 0, arr.length - 1);
        print(arr);
    }

    private void doSort(int[] arr, int l, int r) {
        if (l < r) {
            int index = adjust(arr, l, r);
            doSort(arr, 0, index - 1);
            doSort(arr, index + 1, r);
        }
    }

    private int adjust(int[] arr, int l, int r) {
        int pivot = arr[l];
        while (l < r) {
            while (l < r && arr[r] >= pivot) {
                r--;
            }

            if (l < r) {
                arr[l] = arr[r];
                l++;
            }
            while (l < r && arr[l] <= pivot) {
                l++;
            }

            if (l < r) {
                arr[r] = arr[l];
                r--;
            }
        }
        arr[l] = pivot;
        return l;
    }
}
